/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 09 - 01
 * Time: 19:54
 */
//牛客 寻找第K大
public class Solution2 {
    //法一 官方推荐方法
    public int findKth (int[] a, int n, int K) {
        if(n == 0) return -1;
        return quickSortF(a, 0, n - 1, K);
    }
    private int quickSortF(int[] array, int left, int right, int k) {//快速排序成从大到小
        if(left == right) return array[left];
        int pivot = getPivot(array, left, right);
        if(pivot + 1 == k) return array[pivot];
        if(pivot + 1 > k) {
            return quickSortF(array, left, pivot - 1, k);

        }
        return quickSortF(array, pivot + 1, right, k);
    }
    private int getPivot(int[] array, int left, int right) {
        int key = array[left];
        while (left < right) {
            while (left < right && array[right] <= key) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] >= key) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }
}
